package com.itheima.algorithm.datastructure;

/**
 * 查找链表中间的节点
 * @Author: zhangshao
 * @Since: 2024/4/30 16:17
 */
public class Leetcode876 {

	/**
	 * 快慢指针法
	 * @param head
	 * @return
	 */
	public static ListNode middleNode(ListNode head) {
		ListNode p1 = head;
		ListNode p2 = head;
		//短路，必须先判断p2!=null
		while (p2 != null && p2.next != null) {
			p1 = p1.next;
			p2 = p2.next;
			p2 = p2.next;
		}
		return p1;

	}

	public static void main(String[] args) {
		ListNode head1 = ListNode.of(1, 2, 3, 4, 5);
		System.out.println(middleNode(head1));
		ListNode head2 = ListNode.of(1, 2, 3, 4, 5, 6);
		System.out.println(middleNode(head2));
	}
}
